package 基数排序;

import java.util.Arrays;

/**
 * @author ljb
 * @version 1.0
 * @Date 2024/11/25
 */
// 基数排序
// 测试链接 : https://leetcode.cn/problems/sort-an-array/
public class Code02_RadixSort {

    // 可以设置进制，不一定10进制，随你设置
    public static int BASE = 10;
    public static int MAXN = 80001;
    public static int[] help = new int[MAXN];
    public static int[] cnts = new int[BASE];

    public static int[] sortArray(int[] nums) {
        if(nums.length > 1){
            // 如果会溢出，那么要改用long类型数组来排序
            int n = nums.length;
            // 找到数组中的最小值
            int min = nums[0];
            for(int i = 1; i < n; i++){
                min = Math.min(min, nums[i]);
            }
            int max = 0;
            for(int i = 0; i < n; i++){
                // 数组中的每个数字，减去数组中的最小值，就把arr转成了非负数组
                nums[i] -= min;
                // 记录数组中的最大值
                max = Math.max(max, nums[i]);
            }
            // 根据最大值在BASE进制下的位数，决定基数排序做多少轮
            radixSort(nums, n, bits(max));
            // 数组中所有数都减去了最小值，所以最后不要忘了还原
            for(int i = 0; i < n; i++){
                nums[i] += min;
            }
        }
        return nums;
    }

    // 返回number在BASE进制下有几位
    public static int bits(int max){
        int ans = 0;
        while(max > 0){
            max /= BASE;
            ans++;
        }
        return ans;
    }

    // 基数排序核心代码
    // arr内要保证没有负数
    // n是arr的长度
    // bits是arr中最大值在BASE进制下有几位
    public static void radixSort(int[] arr, int n, int bits){
        // 理解的时候可以假设BASE = 10
        for(int offset = 1; bits > 0; offset *= BASE, bits--){
            Arrays.fill(cnts, 0);
            for(int i = 0; i < n; i++){
                // 数字提取某一位的技巧
                cnts[(arr[i] / offset) % BASE]++;
            }
            // 处理成前缀次数累加的形式
            for(int i = 1; i < BASE; i++){
                cnts[i] = cnts[i] + cnts[i-1];
            }
            for(int i = n-1; i >= 0; i--){
                // 前缀数量分区的技巧
                // 数字提取某一位的技巧
                help[--cnts[(arr[i] / offset) % BASE]] = arr[i];
            }
            for(int i = 0; i < n; i++){
                arr[i] = help[i];
            }
        }
    }
}
